//
// Created by denglibin on 2020/6/24.
//
/**
 * 快速排序， 先从右往左找，再从左往右找
 */
#include "../header/sort.h"

static void do_quick_sort(int arr[], int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int low = start;
    int high = end;
    int base = arr[low]; // 将第一个数作为基准
    while (low < high)
    {
        // 从右往左找，直到找到一个比基准小的数
        while (arr[high] > base && low < high)
        {
            high--;
        }
        // 从左往右找，直到找到一个比基准大的数
        while (arr[low] <= base && low < high)
        {
            low++;
        }
        // 交换
        swap_num(arr + low, arr + high);
    }
    // low和high碰头了，交换，这样low左表 的数都比arr[low]小，右边都比arr[low]大
    swap_num(arr + start, arr + low);
    //  递归左边
    do_quick_sort(arr, start, low - 1);
    // 递归右边
    do_quick_sort(arr, low + 1, end);
}
/**
 * 快速排序
 * @param arr
 * @param len
 */
static void quick_sort(int arr[], int len)
{
    do_quick_sort(arr, 0, len - 1);
}

static int main5()
{
    int arr[5] = {3, 4, 5, 1, 2};
    quick_sort(arr, 5);
    print_arr(arr, 5);
    return 0;
}
